package leetcode每日一题;

/**
 * 1. 问题描述
 *      有一个二维矩阵A 其中每个元素的值为0或1。
 *      移动是指选择任一行或列，并转换该行或列中的每一个值：将所有 0 都更改为 1，将所有 1 都更改为 0。
 *      在做出任意次数的移动后，将该矩阵的每一行都按照二进制数来解释，矩阵的得分就是这些数字的总和。
 *      返回尽可能高的分数。
 *
 * 2. 算法分析
 *      题目含义：
 *             我们有一个只含有0,1数字的矩阵,每次我们只能选择其中一行或者一列
 *             将这一行种的0换成1,1换成0,经过若干次转化之后将每一行看成一个二
 *             进制数字,将这个二进制转化为10进制,最终求出每一行的十进制的数字之
 *             和,返回一个尽可能高的分数
 *
 *         算法分析：
 *             为了尽可能的分数高，我们希望矩阵中的1元素比较多,但是有些情况下我
 *             们无法做到将所有元素转化为1
 *             对于示例给出的一个具体的例子,我们进行如下的操作：
 *                 将第1行移动 [0,0,1,1] ---> [1,1,0,0]
 *                 此时的矩阵变为了
 *                     [1,1,0,0]
 *                     [1,0,1,0]
 *                     [1,1,0,0]
 *                 在分别移动第3列和第4列
 *                     [1,1,1,1]
 *                     [1,0,0,1]
 *                     [1,1,1,1]
 *                 这就是最大得分
 *             我们可以移动的行列之和为 n+m (n为行 m为列)
 *             移动的次数是未知的,由于我们需要得到尽可能高的分数，这可能会暗示我们使用
 *             贪心算法来求解此题,虽然贪心算法不一定得到最优解，但是可以得到在某一个贪
 *             心条件下的最优解,此题的贪心条件就是尽可能的将0变为1
 *             穷举的话主要是不确定移动的次数，所以我们无法将所有的情况列举出来
 *
 *         具体的算法思路：(可能不正确)
 *         大致思路如下：
 *             先扫描行，如果行首元素为0，我们就移动元素，因为行首元素才是确定这一行的主体
 *             这一行的行首元素为1，其余为0，比行首元素为0，其余均为1要大，假设行为n，
 *             则 2^n 与 2^(n-1) + ... + 1 = 2^n -1所以这是第一次扫描
 *
 *             第二次扫描二维数组的列，由于位于同一列的，其二进制的部分是一样的，所以1越多，等分
 *             越多，所以，我们需要判断当前第j列中的1的元素个数与0的元素个数，如果0多，则移动着一
 *             列
 *
 *             最终对移动之后的二维数组进行10进制求和即可(吐槽：相当丑陋的代码)))
 *
 *        分析上述的时间复杂度：假设行为n 列为m
 *          首先第一次扫描行时间复杂度为O(n*m)
 *          第二次扫描列由于扫描列中我们使用了两个for循环，第一个for为找到当前列的1的个数，第二个for为移动当前列
 *          所以时间复杂度为O(m*(n+n))
 *          最后遍历二维数组将其转化为10进制求和O(n*m)
 *          所以最终的时间复杂度为O(n*m+n*m+m*(2n)) = O(4*n*m) 这个时间复杂度还是非常高的近似于平方
 *
 *        上述最主要的不是代码的实现，而是思路的转变，因为题目并没有明确说明我们需要移动几次数组，在这种情况下我们移动几次
 *        才能是得分最大呢?所以我们需要将问题转化成什么样的我们才可以使得矩阵的得分最大?而不是去一开始就考虑到底移动即此，
 *        实际上上述我们对行扫面一遍，满足要求的移动，列扫描一遍，满足要求的移动。这才是这道题的难点所在
 *
 *     优化上述算法：
 *       1. 第一个优化 幂的计算
 *          实际上计算机底层在计算乘法的时间消耗是比较大的，由于计算机的本质是0，1二进制，所以有些时候如果可以采用位运算
 *          来计算某些值会比直接进行数字运算快，例如此题我们需要频繁的计算2的幂，所以此时我们可以采用  1 << m == 2^m
 *
 *       2. 下面的代码中有许多for循环，思考是否有多余的for循环?
 *          在上述的分析下，我们如果当前行的行首为0，我们移动这一行，当所有的行首的元素为1时，我们考虑列
 *          如果当前列的元素中1的元素比0少，我们就移动着一列，由于每一列的元素在数组中的贡献值相同的，所以
 *          我们只需要计算出每一列中1的个数，我们就可以求出当前列对于整个数组的贡献值，最终将所有的值相加就是
 *          整个数组翻转之后的最大值，实际上我们并不需要真正的移动数组，仅仅判断即可，算出每一列的1的个数，这样就
 *          极大的简化了下面的代码
 *          初始化时我们可以直接将第一列直接算出来，因为最终移动的结果中所有的行首一定为1
 *
 * 3. 代码实现
 */
@SuppressWarnings("all")
public class 反转矩阵之后的得分 {
    public static void main(String[] args) {
        int[][] A = {{0,0,1,1},{1,0,1,0},{1,1,0,0}};
        System.out.println(matrixScore2(A));
    }

    public static int matrixScore(int[][] A){
        int row = A.length; // 行数
        int col = A[0].length; // 列数
        int maxscore = 0; // 记录最大得分
        // 扫描行
        for(int i = 0; i < row; i++) {
            if(A[i][0] == 0) {
                // 当前第i行第一个元素为0，移动这一行
                for(int j = 0; j < col; j++) {
                    A[i][j] = (A[i][j] == 0) ? 1 : 0;
                }
            }
        }
        //  扫描列
        for (int j = 0; j < col; j++) {
            int ones = 0; // 记录第j列中1的个数
            for (int i = 0; i < row; i++) {
                ones += (A[i][j] == 1) ? 1 : 0;
            }
            // 判断
            if (ones < row - ones) {
                for (int i = 0; i < row; i++) {
                    A[i][j] = (A[i][j] == 0) ? 1 : 0;
                }
            }
        }
        // 计算得分 并输出矩阵
        for(int i = 0; i < row; i++) {
            int tempscore = 0; // 计算第i行分数
            for(int j = 0; j < col; j++) {
                tempscore += A[i][j] * (1 << col-j-1);
            }
            maxscore += tempscore;
        }
        return maxscore;
    }

    /**
     * 对上述代码的优化
     * @param A
     * @return
     */
    public static int matrixScore2(int[][] A) {
        int row = A.length; int col = A[0].length;
        int maxscore = row * (1 << col - 1);
        for(int j = 1; j < col; j++) {
            int ones = 0;
            for(int i = 0; i < row; i++) {
                /**
                 * 解释下面代码的含义：
                 * 如果当前行的行首为0
                 *      ones += A[i][j]
                 * 如果当前行的行首为1
                 *      ones += 1 - A[i][j]
                 *  为什么?
                 *  首先由于元素只有1，或者0，所以直接让ones加上当前A[i][j]即可，即求出列的元素和就是当前列的
                 *  1的元素个数，但是此时我们需要判断当行的首位是否位0，如果为零，我们需要移动当前行，即1变为0
                 *  0变位1，所以此时我们需要加上1 - A[i][j]，如果不需要直接加上A[i][j]
                 */
                ones += (A[i][0] == 0) ? A[i][j] : (1 - A[i][j]); // 主要是理解这一行代码
            }
            maxscore += Math.max(ones,row-ones)*(1 << col - j - 1);
        }
        return maxscore;
    }
}
